#include "stdio.h"
#include "malloc.h"
typedef struct node
{
	float coef;
	int exp;
	struct  node *next;
}polynode;
polynode *pa,*pb;

polynode *CreatePolym(int m);
void polyadd (polynode *pa,  polynode *pb);
void ShowPolym(polynode* head);

int main()
{
	printf("Please input coef and exp of PA:\n");
	pa=CreatePolym(4);
	printf("Polym A is: ");
	ShowPolym(pa);

	printf("Please input coef and exp of PB:\n");
	pb=CreatePolym(3);
	printf("Polym B is: ");
	ShowPolym(pb);

	polyadd(pa,pb);
	printf("Polym A+B is: ");
	ShowPolym(pa);
}

polynode *CreatePolym(int m)     /*改进尾插法*/
{
	float c;
	int e;
	polynode *head,*s,*r;
	head=(polynode *)malloc(sizeof(polynode));  /*生成头结点*/
	head->exp=9999;
	r=head;                   /*尾指针初值指向头结点*/
	for (int i=0;i<m;i++)
	{
		scanf("%f%d",&c,&e);
		s=(polynode *)malloc(sizeof(polynode));  /*生成新结点*/
		s->coef=c;
		s->exp=e;
		r->next=s;     /*新结点插入表尾*/
		r=s;           /*尾指针r指向新的表尾*/
	}
	r->next=NULL;
	return head;
}         /*CreatePolym*/

void polyadd (polynode *pa,  polynode *pb)
{
	polynode *qa,*qb,*pre,*r ;
	float x;
	pre=pa;
	qa=pa->next;
	qb=pb->next;    /*指向第一个结点*/

	while(qa&&qb)
	{
		if(qa->exp<qb->exp) 	/*pa指数小于pb指数的情况*/
		{pre=qa;  qa=pre->next;}   /* qa 指后移*/
		else if (qa->exp== qb->exp) /*pa,pb指数相同的情况*/
			{
				x = qa->coef + qb->coef;  /*系数相加*/
				if ( x!=0 )
				{qa->coef = x;  pre = qa; } /*系数不为0*/
				else
				{pre->next=qa->next;  free(qa);} /*系数为0*/
				qa = pre->next;  /* qa 指针后移*/
				r = qb;
				qb=qb->next;         /*qb 指针后移*/
				free ( r );      /* 释放pb中的结点*/
			}
			else  if (qa->exp>qb->exp)   /*pa指数小于pb指数的情况*/
					{
						r = qb->next;
						qb -> next = qa;
						pre -> next = qb;  /* qb 连入pa*/
						pre = qb;
						qb = r;     /* qb 指针后移*/
					}
	} /*while 循环结束 */
	if (qb!=NULL) pre->next=qb;  /*pb 中有剩余结点连入pa中*/
	free(pb);  /*释放pb头结点*/
}          /*polyadd 结束*/

void ShowPolym(polynode* head)
{
	polynode *p;
	p=head;
	p=p->next;     /*对有头结点的链表进行特殊处理*/
	while(p->next!=0)
	{
		printf("%5.1fx%d+",p->coef,p->exp);
		p=p->next;
	}
	printf("%5.1fx%d\n",p->coef,p->exp);
}
